package Heap;

import java.util.Arrays;
import java.util.Random;

public class HeapMax {
    private int[] arr;
    private int count;
    private int[] indexArr;

    public static void main(String[] args) {
        HeapMax heapMax = new HeapMax(15);
        for (int i = 0; i < 15; i++) {
            heapMax.insert(new Random().nextInt(100));
        }
        System.out.println(Arrays.toString(heapMax.arr));
        while (heapMax.count > 0) {
            heapMax.sort();
        }
    }

    public void sort() {
        int max = exactMax();
        System.out.println(max);
        swap(0, count);
        count--;
        shiftDown(0);
    }

    public int exactMax() {


        return arr[0];
    }

    HeapMax(int capacity) {
        arr = new int[capacity + 1];
        count = 0;
    }

    public boolean isEmpty() {
        return count == 0;
    }

    public void insert(int val) {
        //在尾节点插入
        arr[count + 1] = val;
        //维持count 当然，优美的的写法当然是arr[count++]=val啦啦啦啦 - -！
        count++;
        //对末尾的数进行上浮操作
        shiftUp(count);
    }

    //下沉操作
    public void shiftDown(int k) {
        //传入k，先让这个k的子节点进行比较，我们选取子节点中最大的那个进行比较
        int j = 2 * k + 1;
        while (j <= count) {
            //选子节点
            if (j + 1 <= count && arr[j] < arr[j + 1]) {
                j = j + 1;
            }
            //判断产生交换
            if (arr[j] > arr[k]) {
                swap(j, k);
                k = j;
            } else {
                break;
            }

        }
    }

    //上浮操作
    public void shiftUp(int k) {
        //遍历该值和它的母子节点的值，假如子节点大于母节点，我们上浮操作，并对k进行维护
        while (k > 0 && arr[k / 2] < arr[k]) {
            swap(k, k / 2);
            k /= 2;
        }
    }

    public void swap(int i, int j) {
        int temp;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
